package com.adee.algorithm.learn;

import com.adee.algorithm.utils.Util;

/**
 * 在一个数组中，找出前n个大数，降序排列
 */
public class Test003_topN {
    public static void main(String[] args) {
        int[] arr = Util.genArr(20);
        Util.print("原始数组：", arr);
        Util.sortR(arr);
        Util.print("降序排序后：", arr);
        Util.print("top N：", topN(arr, 5));
    }

    /**
     * 算法一、取出前N个元素，放到一个新数组arrN[N]中，并从小到大排好序，
     * 然后从第N+1个元素开始向后遍历数组，如果在arrN[0]~arrN[N-1]之间，
     * 就将元素插入arrN中（使用二分查找法找到合适位置）。
     * 时间复杂度为：O(N*len)
     */
    public static int[] topN(int[] arr, int n) {
        int len = arr.length;
        if (n > len) {
            throw new RuntimeException(String.format("%d 超过了数组长度 %d", n, len));
        }
        int[] arrN = new int[n];
        System.arraycopy(arr, 0, arrN, 0, n);
        Util.sortR(arrN); // 降序排序
        for (int i = n; i < len; i++) {
            if(arr[i] >= arrN[0] && arr[i] <= arrN[n-1]) {
                // 二分法将arr[i]插入arrN中
                int k = Test001_binarySearch.binarySearch4(arrN, arr[i]);
                System.arraycopy(arrN, k, arrN, k+1, len-k-1);
                arrN[k] = arr[i];
            }
        }
        return arrN;
    }


}
